// https://www.lintcode.com/problem/load-balancer/description
// 526. 负载均衡器
// 为网站实现一个负载均衡器，提供如下的 3 个功能：

// 添加一台新的服务器到整个集群中 => add(server_id)。
// 从集群中删除一个服务器 => remove(server_id)。
// 在集群中随机（等概率）选择一个有效的服务器 => pick()。
// 样例
// 最开始时，集群中一台服务器都没有。

// add(1)
// add(2)
// add(3)
// pick()
// >> 1         // 返回值是随机的，这里是 1 或者 2 或者 3 都正确。
// pick()
// >> 2
// pick()
// >> 1
// pick()
// >> 3
// remove(1)
// pick()
// >> 2
// pick()
// >> 3
// pick()
// >> 3



// 思路：
// • 要在o(1)的时间内插入删除，只能hash。那hash可以getRandom吗？
// – 不太好做
// • 什么数据结构比较好getRandom？
// – 数组
// • 考虑hash与数组结合起来用，hash插入一个，数组也插入一个。那么问题
// 来了，数组删除元素怎么办？
// – 与最后插入的一个元素交换
// • 那怎么o(1)时间在数组中找到要删除元素（要交换）的位置？
// – 用hash将元素的位置记下来

// 算法：
// • 插入：
// – 数组末尾加入这个元素
// – Hash这个元素存下数组中的下标
// • 删除：
// – 通过hash找到这个元素在数组中的位置
// – 数数组中这个元素和数组的末尾元素交换，交换后删除
// – Hash中删除这个元素，更新数组原末尾元素现在在数组中的位置
// • Pick：
// – 数组中random一个返回

// 考点：
// • 两种数据结构的综合应用

class LoadBalancer {
public:
    map<int, int> dict;
    vector<int> servers;
    LoadBalancer() {
        // do intialization if necessary
    }

    /*
     * @param server_id: add a new server to the cluster
     * @return: nothing
     */
    void add(int server_id) {
        int m = servers.size();
        dict[server_id] = m;
        servers.push_back(server_id);
    }

    /*
     * @param server_id: server_id remove a bad server from the cluster
     * @return: nothing
     */
    void remove(int server_id) {
        int idx = dict[server_id];
        int m = servers.size();
        dict[servers[m - 1]] = idx; // 不要忘了
        servers[idx] = servers[m - 1];
        servers.pop_back();
        dict.erase(dict.find(server_id));
    }

    /*
     * @return: pick a server in the cluster randomly with equal probability
     */
    int pick() {
        int m = servers.size();
        int idx = rand() % m;
        return servers[idx];
    }
};